﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DynamicProgramming
{
    /* Problem description
     * 
     * Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), 
     * write code to calculate the number of ways of representing n cents.
     * 
     * Original link: Cracking interview (the 150 questions), under section recursion, section 8.7 
     */

    class MakingChange_V2
    {
        /* Algorithm
         * 
         * We know that makeChange(100):
         *   =makeChange(100 using 0 quarters) + makeChange(100 using 1 quarter) + makeChange(100 using 2 quarter) + makeChange(100 using 3 quarter) + makeChange(100 using 4 quarter)
         * Can we reduce this further? Yes!
         *   = makeChange(100 using 0 quarters) + makeChange(75 using 0 quarter) + makeChange(50 using 0 quarters) + makeChange(25 using 0 quarters) + 1
         * Now what? We’ve used up all our quarters, so now we can start applying our next biggest denomination: dime
         * 
         */

        public int GetWaysOfChange(int target, int denom)
        {
            int ways = 0;
            int next_denom = 0;

            switch (denom)
            {
                case 25:
                    next_denom = 10;
                    break;
                case 10:
                    next_denom = 5;
                    break;
                case 5:
                    next_denom = 1;
                    break;
                case 1:
					return (target % denom == 0) ? 1 : 0; // in more general case (the last coin face value isn't 1), return 1 as "target % denom == 0". Otherwaise return 0
            }

            for (int i=0; i*denom <= target; i++)
            {
                ways += GetWaysOfChange((target - i*denom), next_denom);
            }

            return ways;
        }

        static void Main(string[] args)
        {
            MakingChange_V2 mv2 = new MakingChange_V2();

            int target = 1234;
            int ways = mv2.GetWaysOfChange(target, 25);

            Console.WriteLine("There are {0} of ways to split {1}", ways, target);
            Console.ReadKey();
        }
    }
}
